package 左哥算法.ch03堆;

import org.junit.Test;
import 左哥算法.compare.贪心.Problem07_ChooseWork;

import java.util.*;

import static org.junit.Assert.assertArrayEquals;

public class Ch04一些堆的玩法 {

    @Test
    public void test(){
        double target=275.6;
        double k=27.4;
        double c=11.9;
        double[][] gasStation={
                {0,2.8},
                {102,2.9},
                {220,2.2},
        };
        System.out.println(fun1(target,c,k,gasStation));
    }

    /**
     * T5221：指定你到目的地的距离target
     * 以及你油箱的容量c，每升油能走的距离k
     * 现有n+1个加油站（多出来的那个是在起点位置）
     * 每个加油站距起点的位置为 gasStation[i][0]，加油站每升油对应的价格为gasStation[i][1]。
     * 求你到达目的地所需的最少油费
     * 思路：
     *      将所有的加油站以距离为比较对象放入一个小根堆distanceQueue中。
     *      将解锁的油站以价格为比较对象放入小根堆priceQueue中。
     *      1.以满油情况下将距离堆中能解锁的油站放入 价格堆 中。（需要在目的地之内）
     *      2.用当前油站与价格堆顶油站的价格对比。(如果价格堆中为空，则表示不可抵达下一个油站)
     *          如果当前油价低于堆顶油价：则在当前油站加满(或加到刚好抵达目的地)
     *          如果当前油价高于堆顶油价：则在当前油站加到刚好能开到堆顶油站的价格
     *      3.开到堆顶油站后，将小于当前距离的油站从价格堆中移除。再重复1，2
     */
    public double fun1(double target,double c,double k,double[][] gasStation){
        PriorityQueue<double[]> distanceQueue=new PriorityQueue<>((a,b)->{
            if (a[0]==b[0]){
                return 0;
            }
            return (a[0]-b[0])<0?-1:1;
        });
        PriorityQueue<double[]> priceQueue=new PriorityQueue<>((a,b)->{
            if (a[1]==b[1]){
                return 0;
            }
            return (a[1]-b[1])<0?-1:1;
        });
        for (int i = 1; i < gasStation.length; i++) {
            distanceQueue.add(gasStation[i]);
        }
        double resMoney = 0;      //最后的金额
        double[] curStation = gasStation[0];    //当前油站
        double currDistance=0;
        double restGas = 0;   //剩余油量

        do {
            while (!distanceQueue.isEmpty() && curStation[0] + c * k >= distanceQueue.peek()[0]) {
                if (distanceQueue.peek()[0] <= target) {
                    priceQueue.add(distanceQueue.poll());   //解锁到价格堆中
                }
            }
            double[] next =priceQueue.poll();  //没有油站了
            double needGas = 0;  //需要在当前节点加多少油
            if (curStation[0] + c * k >= target) {    //当前油站能抵达终点
                //当前油站能抵达终点，判断是在该油站加到终点还是在下一个
                needGas = curStation[1] <= next[1] ? (target - curStation[0]) / k - restGas : (next[0] - curStation[0]) / k - restGas;
            } else {
                //当前油站不能抵达终点，判断是在该油站加满还是在下一个
                needGas = curStation[1] <= next[1] ? c - restGas : (next[0] - curStation[0]) / k - restGas;
            }
            resMoney += curStation[1] * needGas;
            restGas = restGas + needGas - next[0] / k;  //加油到移动到下一个节点的量
            curStation = restGas*k>=target?curStation:next; //直接抵达终点或到下一个油站
            currDistance=curStation[0]+restGas*k;
            while (!priceQueue.isEmpty()&&priceQueue.peek()[0]<curStation[0]){
                priceQueue.poll();
            }
        } while (!priceQueue.isEmpty());

        if (curStation[0]+c*k<target){
            return -1;
        }else if(currDistance<target){
            double needGas=(target-curStation[0])/k;
            resMoney+=needGas*curStation[1];
        }
        return resMoney;
    }

    /**
     * 前K个高频单词
     */
    @Test
    public void ch02(){
        String[] words={"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        int k=4;
        System.out.println(topKFrequent(words, k));
    }
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        List<String> list=new ArrayList<>(k);
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0)+1);
        }
        TreeSet<String> set=new TreeSet<>((o1, o2) -> {
            Integer size1 = map.get(o1);
            Integer size2 = map.get(o2);
            if (size1==size2){
                return o1.compareTo(o2);
            }
            return size2-size1;
        });
        map.forEach((key,val)->{
            if (set.size()<k){
                set.add(key);
                return;
            }
            if (set.comparator().compare(set.last(),key)>0) {
                set.add(key);
            }
        });
        list.addAll(set);
        return list;
    }

    /**
     * ch03：
     * 给定一些工作，每个工作都有一个报酬和难度。
     * 再给定一个数组，代表每个求职者的能力。
     * 求出每个求职者能获得的最大报酬.
     */
    @Test
    public void testGetMoneys() {
        // Test case 1
        int[][] jobs1 = {{1, 2}, {3, 4}, {5, 6}};
        int[] ability1 = {2, 3, 4};
        int[] expected1 = {2,4, 4};
        int[] result1 = getMoneys(jobs1, ability1);
        assertArrayEquals(expected1, result1);

        // Test case 2
        int[][] jobs2 = {{5,12}, {16,3}};
        int[] ability2 = {4, 5, 17};
        int[] expected2 = {0, 12, 12};
        int[] result2 = getMoneys(jobs2, ability2);
        assertArrayEquals(expected2, result2);

    }

    /**
     * @param jobs：工作的数量，二维的0位置代表难度。1位置代表报酬。
     * @param ability：每个求职者的能力
     * @return：每个求职者对应的工作报酬
     */
    public int[] getMoneys(int[][] jobs, int[] ability){
        int[] res=new int[ability.length];
        PriorityQueue<int[]> locked=new PriorityQueue<>((o1, o2) -> o1[0]-o2[0]);   //未解锁的工作
        PriorityQueue<int[]> work=new PriorityQueue<>((o1, o2) -> o2[1]-o1[1]); //已解锁的工作
        PriorityQueue<int[]> abilityQueue=new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]); //每个求职者的能力以及
        //对求职者能力排序，因为需要保存原先的顺序，所以用二维数组存储
        for (int i = 0; i < ability.length; i++) {
            abilityQueue.add(new int[]{i,ability[i]});
        }
        Arrays.stream(jobs).forEach(locked::add);
        while (!abilityQueue.isEmpty()) {
            int[] seeker = abilityQueue.poll();
            while (!locked.isEmpty()&&seeker[1]>=locked.peek()[0]){ //解锁工作
                work.add(locked.poll());
            }
            if (!work.isEmpty()){   //从解锁的工作里挑一个最大的
                res[seeker[0]]=work.peek()[1];
            }
        }
        return res;
    }

    @Test
    public void compare(){
        int count=100;
        Random r=new Random();
        while (count-- > 0) {
            int[][] jobs = new int[r.nextInt(10)+1][2];
            int[] ability = new int[r.nextInt(10)+1];
            for (int[] job : jobs) {
                job[0]=r.nextInt(100)+1;
                job[1]=r.nextInt(100)+1;
            }
            for (int i = 0; i < ability.length; i++) {
                ability[i] = r.nextInt(100) + 1;
            }
            int[] adapter = Problem07_ChooseWork.adapter(jobs, ability);
            int[] moneys = getMoneys(jobs, ability);
//            int[] moneys = null;
            if (!Arrays.equals(moneys, adapter)) {
                System.out.println("error");
                System.out.println("jobs:");
                Arrays.stream(jobs).forEach(o->System.out.println(Arrays.toString(o)));
                System.out.println("ability:"+Arrays.toString(ability));
                System.out.println("res:"+Arrays.toString(moneys));
                System.out.println("ans:"+Arrays.toString(adapter));
            }
        }
        System.out.println("end");
    }
}
